import java.util.ArrayList;

/*
题目描述：最小的 k 个数
方法：
1. 排序  O(nlogn)
2. partition变形
3. 用最大堆保存着k个数
下面实现partition(这种方法会破坏原数组！！)
 */
public class E40_1 {
    public static void main(String[] args) {
        int[] array = {4,5,1,6,2,7,3,8};
        ArrayList<Integer> res = GetLeastNumbers_Solution(array, 4);
        System.out.println(res);
    }

    public static ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        if(input == null || input.length <= 0 || k <= 0 || k > input.length){
            return res;
        }
        int start = 0;
        int end = input.length - 1;
        int index = partition(input, start, end);
        while(index != k - 1){
            if(index > k - 1){
                end = index - 1;
                index = partition(input, start, end);
            }
            else{
                start = index + 1;
                index = partition(input, start, end);
            }
        }
        for(int i = 0; i < k; i++){
            res.add(input[i]);
        }
        return res;
    }

    public static int partition(int[] input, int start, int end){
        int pivot = input[start];
        while(start < end){
            while(start < end && input[end] >= pivot){
                end--;
            }
            input[start] = input[end];
            while(start < end && input[start] <= pivot){
                start ++;
            }
            input[end] = input[start];
        }

        input[start] = pivot;
        return start;
    }
}
